#include "stdafx.h"
#include "InsertionSort.h"

void InsertionSort(int Arr[], int start, int end)
{
    int n = end - start + 1;
    for(int unSortInd = start+1; unSortInd <= end; ++unSortInd)
    {
        int sortInd = unSortInd - 1;
        int currSortValue = Arr[unSortInd];
        while(sortInd >= start && currSortValue < Arr[sortInd])
        {
            Arr[sortInd + 1] = Arr[sortInd];
            --sortInd;
        }
        Arr[sortInd + 1] = currSortValue;
    }
}

void InsertionSortRecursive(int Arr[], int start, int end)
{
    int n = end - start + 1;
    if(n > 1)
    {
        InsertionSortRecursive(Arr, start, end-1);

        // The key that is to be inserted on to sorted array Arr[start .. end-1] in the previous step.
        int currSortValue = Arr[end]; 
        int sortInd = end-1;
        while(sortInd >= start && currSortValue < Arr[sortInd])
        {
            Arr[sortInd + 1] = Arr[sortInd];
            --sortInd;
        }
        Arr[sortInd + 1] = currSortValue;
    }
}
